/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        auto dfs = [&](auto fun, int l,int r)->TreeNode*{
            if(l > r){
                return nullptr;
            }
            int mid = (l + r) / 2;
            TreeNode* node = new TreeNode (nums[mid]);
            node->left = fun(fun,l,mid - 1);
            node->right = fun(fun,mid + 1,r);
            return node;
        };
        return  dfs(dfs,0,n - 1);
    }
};




/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        stack<ListNode*> st;
        ListNode* ans = nullptr;
        ListNode* left = nullptr;
        ListNode* mid = nullptr;
        ListNode* right = nullptr;

        while(head != nullptr){
            if(head->val < x){
                if(ans == nullptr){
                    ans = head;
                    left = head;
                }else{
                    left->next = head;
                    left = head;
                }
            }else{
                if(mid == nullptr){
                    mid = head;
                    right = head;
                }else{
                    right->next = head;
                    right = head;
                }
            }
            head = head->next;
        }
        if(ans == nullptr){
            return mid;
        }else if(mid == nullptr){
            left->next = nullptr;
            return ans;
        }else{
            left->next = mid;
            right->next = nullptr;
            return ans;
        }
    }
};